package E_2024;

import java.util.*;

/*
一、题目描述
    给定一个有向图，图中可能包含有环，图使用二维矩阵表示，每一行的第一列表示起始节点，第二列表示终止节点，如 [0, 1] 表示从 0 到 1 的路径。
    每个节点用正整数表示。
    求这个数据的首节点与尾节点，题目给的用例会是一个首节点，但可能存在多个尾节点。同时图中可能含有环。如果图中含有环，返回 [-1]。
    说明：入度为 0 是首节点，出度为 0 是尾节点。
二、输入描述
    第一行为后续输入 A 的键值对 Q 数量 (N ≥ 0)
    第二行为 2N 个数字。每两个为一组一个起点，一个终点，如：
    4
    1 2 2 3 3 1 3 4
三、输出描述
    输出一个首节点和尾节点。如果有多个尾节点，按从大到小的顺序输出。
    备注
    如果图有环，输出为 [-1]
    所有输入均合法，不会出现不匹配的数据
四、测试用例
测试用例1：
    1、输入
    4
    0 1 0 2 1 2 2 3
 */
public class E_200_20 {
    public static void main(String[] args) {
        ans(new int[]{1,2,2,3,3,1,3,4});
        ans(new int[]{0,1,0,2,1,2,2,3});
    }
    public static void ans(int[] arr){
        //统计入度，首节点入度应该为0，当无入度0时表示有环
        Map<Integer,Integer> in = new HashMap<>();
        Map<Integer,Integer> out = new HashMap<>();
        for (int i = 0; i < arr.length; i+=2) {
            // 入度统计
            in.putIfAbsent(arr[i], 0);
            in.put(arr[i+1], in.getOrDefault(arr[i+1],0) + 1);
            // 出度统计
            out.putIfAbsent(arr[i+1],0);
            out.put(arr[i], out.getOrDefault(arr[i],0) + 1);
        }
        System.out.println(in);
        System.out.println(out);
        List<Integer> shou = new ArrayList<>();
        int min = 1;
        for (Map.Entry<Integer, Integer> entry : in.entrySet()) {
            if (entry.getValue() == 0) shou.add(entry.getKey());
            min = Math.min(min, entry.getValue());
        }
        if (min > 0) {
            System.out.println( -1 );
            return;
        }
        List<Integer> wei = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : out.entrySet()) {
            if (entry.getValue() == 0) wei.add(entry.getKey());
        }
        wei.sort(Integer::compareTo);
        System.out.print(shou);
        System.out.println(wei);
    }
}
